package 单调栈;

import org.junit.Test;
import sort.前K个高频元素的quickVersion;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/21 15:22
 */
public class lc503下一个更大的元素II {

    /*
     有重复的元素 存在
     而且数组是 循环的 , 这里处理循环,那可太简单了
     */


    public int[] solve(int nums[]){
        int ans[] = new int[nums.length];
        int gt_end = nums[nums.length - 1];
        boolean flag = true;
        Deque<List<Integer>> stack = new ArrayDeque<>();
        for(int i = 0;i < nums.length;i++){
            if(flag && gt_end < nums[i]){
                gt_end = nums[i];  // 当然这里 也可以 记录下标
            }

            while(!stack.isEmpty() && nums[stack.peekLast().get(0)] < nums[i]){

                List<Integer> last = stack.removeLast();
                for(int num : last){
                    ans[num] = nums[i];
                }
            }
            if(nums[stack.peekLast().get(0)] == nums[i]){
                stack.peekLast().add(i);
            }else{
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.addLast(list);
            }
        }

        while(!stack.isEmpty()){
        }

        return ans;
    }


    /*
     有重复元素的话, 直接 堆上去 就可以, 没必要 使用 list

     // 这里处理循环 数组的方式, 是非常值得学习

     1. 复制 原数组 一份, 把copy 的放到原数组的后面
     2. 采用取模的方式
     - 无论那种方式, 都需要遍历 数组两次, 一次是不行的!

     这里需要注意的一点:是 原数组 [1,2,3,4,5]
     拉直后的数组是 [1,2,3,4,5,1,2,3,4]  是这样的, 5后面是 1, 其实数组的长度 是 2 * n - 1
     */


    public int []solution(int nums[]){
        int len = nums.length;
        int ans[] = new int[len];
        Deque<Integer> stack = new ArrayDeque<>();
        Arrays.fill(ans, - 1);
        for(int i = 0;i < len * 2 - 1;i++){
            while(!stack.isEmpty() && nums[stack.peekLast()] < nums[i % len]){ // mod
                Integer last = stack.removeLast();
                ans[last] = nums[i % len];
            }
            stack.addLast(i % len);
        }
//        while(!stack.isEmpty()){
//            ans[stack.removeLast()] = -1;
//        }

        return ans;
    }

    @Test
    public void test(){
        int nums[] = {1,2,3,4,5};
    }


}
